package com.leetcode.hash;

import java.util.HashSet;
import java.util.Set;

//最长连续序列
public class lc_128 {
    public static void main(String[] args) {
        int[] nums = {100,4,200,1,2,3};
        System.out.println(longestConsecutive(nums));
    }

    public static int longestConsecutive(int[] nums) {
        //思路: 放入set集合,使用contains方法,当不存在num-1就直接去获得最大长度,最大长度也是使用contains获取
        if (nums == null || nums.length == 0) {
            return 0;
        }

        //1.将所有数据放入set集合(不需要键值所以不用map,长度可能很长所以不用数组)
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int maxLength = 0;

        for (int num : set) {
            //如果不存在num - 1,说明是这个序列的最低点(1,2,3所有都会遍历一遍)
            if (!set.contains(num - 1)){
                int currentLength = 1;
                //向右遍历获取所有的元素,只要还存在连续的更大值,就继续往后遍历
                while(set.contains(num + 1)){
                    currentLength++;
                    num++;
                }
                //每次都更新最大元素
                maxLength = Math.max(maxLength,currentLength);
            }
        }
        return maxLength;
    }
}
